package com.lwl.Algorithmic_data_structure.class24滑动窗口;

import java.util.LinkedList;

/**
 * @author lwl
 * @Description 给你一个数组，以及一个窗口大小，请你求出窗口划过数组时的最大值集合
 * @date 2023/6/24 21:31
 */
public class Code01SlidingWindowMaxArray {

    public static int[] getSlidingWindowMaxArray(int[] array, int windowSize) {
        if (array == null || windowSize < 1 || array.length < windowSize) {
            return null;
        }
        LinkedList<Integer> maxDoubleQueue = new LinkedList<>();
        int[] res = new int[array.length - windowSize + 1];
        int index = 0;
        for (int R = 0; R < array.length; R++) {
            while (!maxDoubleQueue.isEmpty() && array[maxDoubleQueue.peekLast()] <= array[R]) {
                maxDoubleQueue.pollLast();
            }
            maxDoubleQueue.addLast(R);
            if (R - windowSize == maxDoubleQueue.peekFirst()) {
                maxDoubleQueue.pollFirst();
            }
            if (R >= windowSize - 1) {
                res[index++] = array[maxDoubleQueue.peekFirst()];
            }
        }
        return res;
    }

}
